C2 Triangle rasterization

2026/2/6 · Tech

三角形栅格化

V1 扫描线算法

通过逐行扫描绘制三角形的方法，核心思想是
三角形是”凸多边形“，将三角形切为上下两半
主要步骤如下：

排序顶点（最低-最高），得到长边和短边
短边由两条边组成，从其顶点水平切分三角形
由扫描线的 $y$ 坐标，确定扫描线的 $x$ 的左右边界
依次自底向上逐行绘制扫描线

代码如下：

void triangle(int ax, int ay, int bx, int by, int cx, int cy, TGAImage &framebuffer, TGAColor color) {
    if(ay > by) { std::swap(ax, bx); std::swap(ay, by); }
    if(ay > cy) { std::swap(ax, cx); std::swap(ay, cy); }
    if(by > cy) { std::swap(bx, cx); std::swap(by, cy); }
    int tot_h = cy - ay;

    // 下半部分
    if(ay != by) {
        int seg_h = by - ay;
        for(int y = ay; y <= by; y ++) {
            int ac_x = ax + (cx - ax) * (y - ay) / tot_h;
            int ab_x = ax + (bx - ax) * (y - ay) / seg_h;
            for(int x = std::min(ac_x, ab_x); x < std::max(ac_x, ab_x); x ++) {
                framebuffer.set(x, y, color);
            }
        }
    }

    // 上半部分
    if(by != cy) {
        int seg_h = cy - by;
        for(int y = by; y <= cy; y ++) {
            int ac_x = ax + (cx - ax) * (y - ay) / tot_h;
            int bc_x = bx + (cx - bx) * (y - by) / seg_h;
            for(int x = std::min(ac_x, bc_x); x < std::max(ac_x, bc_x); x ++) {
                framebuffer.set(x, y, color);
            }
        }
    }
}

V2 现代化方法

通过确认每点是否处于三角形内部，从而进行填充的方法。
核心思想是重心坐标的运用，在下一章详细展开
具体步骤如下：

找到三角形的包围盒（bounding box)
- 由左下角和右下角控制
对包围盒中的所有点，检查其是否处于三角形内部
- 若处于，则在此像素点位置填充颜色

这里的每个像素点都是单独处理的，因此这是一种便于并行计算的方法。

代码如下：

/**
 * @brief 现代栅格化算法
 * @note 便于并行计算
 * 
 * @param ax 
 * @param ay 
 * @param bx 
 * @param by 
 * @param cx 
 * @param cy 
 * @param framebuffer 
 * @param color 
 */
void triangle(int ax, int ay, int bx, int by, int cx, int cy, TGAImage &framebuffer, TGAColor color) {
    /* 左下角坐标 */
    int bbminx = std::min(ax, std::min(bx, cx));
    int bbminy = std::min(ay, std::min(by, cy));
    /* 右上角坐标 */
    int bbmaxx = std::max(ax, std::max(bx, cx));
    int bbmaxy = std::max(ay, std::max(by, cy));
    double tot_area = get_signed_area(ax, ay, bx, by, cx, cy);

    for(int x = bbminx; x <= bbmaxx; x ++ ) {
        for(int y = bbminy; y <= bbmaxy; y ++) {
            double alpha = get_signed_area(x, y, bx, by, cx, cy) / tot_area;
            double beta = get_signed_area(x, y, cx, cy, ax, ay) / tot_area;
            double gamma = get_signed_area(x, y, ax, ay, bx, by) / tot_area;

            if(alpha < 0 || beta < 0 || gamma < 0) continue;
            framebuffer.set(x, y, color);
        }
    }
}

重心坐标的计算

有很多方法可以检查一个点/像素是否属于三角形内部。
这里选择重心坐标（barycentric coordinates），因其对后续处理的帮助很大。

在三角形的语境中，重心坐标也称为面积坐标或面坐标 ，因为点 P 相对于三角形 ABC 的坐标等价于 PBC 、 PCA 和 PAB 的面积与参考三角形 ABC 面积的（有符号）比值。

每个三角形 ABC 都有一个带符号的面积值，即正负其面积：
$sarea(ABC)= \pm area(ABC)$
如果沿三角形逆时针方向绕行，则符号为正；如果沿三角形顺时针方向绕行，则符号为负。

设 P 为平面上的一个点， $(λ_1,λ_2,λ_3)$ 为其相对于三角形 ABC 的归一化重心坐标，则
$P = λ_1 A + λ_2 B + λ_3 C$
$λ_1 + λ_2 + λ_3 = 1$
归一化重心坐标也称为面积坐标，因为它们表示三角形有符号面积的比率：
$λ_1 = sarea(PBC) / sarea(ABC)$
$λ_2 = sarea(APC) / sarea(ABC)$
$λ_3 = sarea(ABP) / sarea(ABC)$

面积的计算

这里运用的是鞋带公式 / 高斯面积公式（Shoelace formula）对三角形的面积进行计算：

/**
 * @brief 鞋带公式求三角形面积
 * @note 逆时针求解面积，一般为正
 * 
 * @param ax 
 * @param ay 
 * @param bx 
 * @param by 
 * @param cx 
 * @param cy 
 * @return double 三角形有向面积
 */
double get_signed_area(int ax, int ay, int bx, int by, int cx, int cy) {
    return 0.5 * ((by - ay) * (bx + ax) + (cy - by) * (cx + bx) + (ay - cy) * (ax + cx));
}